#include <bits/stdc++.h>

using namespace std;

// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
// 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
// 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
// 比如如下两棵树
//         __2
//        /
//       1
//       和
//       1__
//          \
//           2
// 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
// 提交这个类

class Codec 
{
public:
    static const int MAXN = 10001;
    TreeNode* q[MAXN];
    int l, r;

    string serialize(TreeNode* root) 
    {
        string ans;
        if(root != nullptr)
        {
            l = r = 0;
            q[r++] = root;
            ans += to_string(root->val) + ",";
            while(l < r)
            {
                root = q[l++];
                if(root->left)
                {
                    ans += to_string(root->left->val) + ",";
                    q[r++] = root->left;
                }
                else ans += "#,";

                if(root->right)
                {
                    ans += to_string(root->right->val) + ",";
                    q[r++] = root->right;
                }
                else ans += "#,";
            }
        }
        return ans;        
    }

    TreeNode* generate(const string& val)
    {
        return val == "#" ? nullptr : new TreeNode(stoi(val));
    }

    TreeNode* deserialize(string data) 
    {
        if(data.empty()) return nullptr;

        vector<string> vals;
        string tmp;
        for(char ch : data)
        {
            if(ch == ',')
            {
                vals.emplace_back(tmp);
                tmp.clear();
            }
            else tmp += ch;
        }

        int index = 0;
        TreeNode* root = generate(vals[index++]);
        l = r = 0;
        q[r++] = root;
        while(l < r)
        {
            TreeNode* cur = q[l++];
            cur->left = generate(vals[index++]);
            cur->right = generate(vals[index++]);
            if(cur->left) q[r++] = cur->left;
            if(cur->right) q[r++] = cur->right;
        }

        return root;
    }
};